COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a06.tex[106,phy] \today\hfill}

\bigskip
An algorithm may fail in four ways:

\smallskip
\display 40pt:(1):
It may halt normally with wrong answers.

\smallskip
\display 40pt:(2):
It may halt on an error condition, like division by zero or requiring more
memory space than is available.

\smallskip
\display 40pt:(3):
It may fail to halt at all, either because it repeats the same situation
or because it goes through infinitely many different situations.

\smallskip
\display 40pt:(4):
It may fail to halt in reasonable time, typically being stopped by intervention
of humans or other programs.

\smallskip
A programmer can ensure correctness of his programs by eliminating the
four causes of failure. Disciplined programming eliminates them by not
letting them into the program from the start. The first cause of failure,
wrong answers, is eliminated by using logic to design the algorithm, 
confirming the logic by finding appropriate invariants. The second cause,
error conditions, is avoided by confirming, from the invariants, that every
function or operation used implicitly or explicitly by the program is used
with arguments for which it works. If a program contains a division, the
invariants must confirm the divisor is not zero. If it contains a subscript,
the invariants must confirm that the subscript lies within its bounds.

The third cause, failure to halt, is avoided in several ways. One method
is to prove termination for each subalgorithm, starting with the simplest
and working up. When a subalgorithm is built up from simpler ones by
definite iteration, conditionals, composition, or non-recursive calls,
it terminates reliably if the simpler ones do. When it uses indefinite
iteration or recursive calls, other methods are required to show termination.
A~very powerful method is to find a formula, containing some of the variables
of the program, that can be shown always to yield an integer that is not
negative (a~``natural'', i.e., counting, number), and to show that at each
step the value of the formula decreases. If the program ran forever, the
sequence of values of the formula would be an infinitely long decreasing
sequence of natural numbers, which is absurd. In Euclid's algorithm, for
example, the formula $2A+B$ decreases at each iteration,
either because $B$ decreases,
or because $A$ is exchanged with $B$ when $A$ is greater than~$B$.
In designing algorithms, we shall often refer to a {\sl decreasing
natural number\/}, meaning just such a formula.

Computer programmers are, as yet, only human, so computer programs continue
to contain faults resulting from typographical errors, logical lapses,
reliance on incorrect information, or whatever. A~serious programmer's
aspiration, though, is to write faultless programs. If you, reader, are
squirming and saying to yourself, ``I~don't need to learn this to program'',
you are quite right. And you don't need to go to medical school to heal
people. It's just that you may be somewhat dangerous to society if you
don't. There are programmers in abundance whom I~would gladly trade
for teams of trained fanatical terrorists; at least the police would be looking
for the terrorists.



\bigskip
\line{\copyright 1984 Robert W. Floyd;
First draft (not published) July 2, 1984\hfil}
%revised: Date; subsequently revised.\hfill}

\bye